package leetcode.dfs;

import java.util.LinkedList;
import java.util.Queue;

//1091. 二进制矩阵中的最短路径
public class ShortestPathBinaryMatrix {

    public int shortestPathBinaryMatrix(int[][] grid) {
        if (grid[0][0] == 1) {
            return -1;
        }
        int[] dx = {1, 1, 1, 0, 0, -1, -1, -1};
        int[] dy = {0, 1, -1, 1, -1, 0, 1, -1};
        int res = 0;
        Queue<int[]> queue = new LinkedList<>();
        int n = grid.length;
        boolean[][] vis = new boolean[n][n];
        queue.offer(new int[]{0, 0});
        vis[0][0] = true;
        while (!queue.isEmpty()) {
            res++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] point = queue.poll();
                if (point[0] == n - 1 && point[1] == n - 1) {
                    return res;
                }
                for (int j = 0; j < 8; j++) {
                    int mx = point[0] + dx[j];
                    int my = point[1] + dy[j];
                    if (mx >= 0 && my >= 0 && mx < n && my < n && grid[mx][my] == 0 && !vis[mx][my]) {
                        vis[mx][my] = true;
                        queue.offer(new int[]{mx, my});
                    }
                }
            }
        }
        return -1;
    }
}
